Field of the Invention
Embodiments of the present invention generally relate to determining a median value of an array using a single instruction, multiple data processing engine.
Description of the Related Art
Computing median values over 3×3, 5×5 and 7×7 blocks of pixels is an important step in many video and vision processing applications. Searching for the best matching patch between two arrays of image data is a common problem in image processing. For example, many stereoscopic imaging systems compute the disparity between left and right images by finding a two-dimensional (2D) patch in the right image that best matches a given 2D patch in the left image. In another example, the alignment of two three-dimensional (3D) point clouds may be accomplished by searching for the best 3D patch matches between the volumes. In another example, video compression algorithms may determine motion between two consecutive images using an optical flow algorithm that matches patches between the two images.
There are several common ways of computing a median value of an array. One method involves sorting all the values in the given block and thus finding the median value. Another method involves creating a histogram for the block and thus finding the median.
Single instruction, multiple data (SIMD) is a well known class of parallel computers. This includes computers with multiple processing elements that perform the same operation on multiple data points simultaneously in response to a single instruction. Thus, such machines exploit data level parallelism, but not concurrency of (separate) operations: there are simultaneous (parallel) computations, but only a single process (instruction) at a given moment. SIMD is particularly applicable to common tasks such as adjusting the contrast in a digital image or adjusting the volume of digital audio. Many modern CPU (central processing unit) designs include SIMD instructions in order to improve the performance of multimedia use.